﻿#define _CRT_SECURE_NO_WARNINGS 1

//给你两个字符串 haystack 和 needle ，
//请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 - 1 。
//
//我们可以让字符串 needle\textit{ needle }needle 与
//字符串 haystack\textit{ haystack }haystack 的所有长度为 mmm 的子串均匹配一次。
//
//为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，
//对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。
//如果所有子串都匹配失败，则返回 −1 - 1−1。




int strStr(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    for (int i = 0; i + m <= n; i++) {
        bool flag = true;
        for (int j = 0; j < m; j++) {
            if (haystack[i + j] != needle[j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return i;
        }
    }
    return -1;
}






int strStr(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    if (m == 0) {
        return 0;
    }
    int pi[m];
    pi[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (needle[i] == needle[j]) {
            j++;
        }
        pi[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}








